package org.czl.gh;

import java.util.Arrays;
import java.util.PriorityQueue;

public class l3377 {
    public static void main(String[] args) {
        System.out.println(minOperations(4, 8));
    }
    static boolean[] prime;
    static {
        prime = new boolean[10002];
        Arrays.fill(prime, true);
        for(int i = 2; i * i < 10002; i++){
            if(prime[i]){
                for(int j = i * i; j < 10002; j+=i){
                    prime[j] = false;
                }
            }
        }
    }
    static int[] dis = new int[10001];
    static boolean[] check = new boolean[10001];
    public static int minOperations(int n, int m){
        if(prime[n] || prime[m])return -1;
        Arrays.fill(dis, Integer.MAX_VALUE);
        Arrays.fill(check, false);
        dis[n] = n;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        queue.add(new int[]{n,n});
        while(!queue.isEmpty()){
            int[] ret = queue.poll();
            int disX = ret[1];
            int x = ret[0];
            if(check[x]){
                continue;
            }
            if(x == m)return disX;
            check[x] = true;
            //从最低位开始 依次进行相加
            int pow10 = 1;
            int v = x;
            while(v > 0){
                int c = v % 10;
                if(c < 9){
                    int temp = x + pow10;
                    if(!prime[temp] && disX + temp < dis[temp]){
                        dis[temp] = disX + temp;
                        queue.add(new int[]{temp, disX + temp});
                    }
                }
                v /= 10;
                pow10 *= 10;
            }
            //最低位开始增加
            pow10 = 1;
            v = x;
            while(v > 0){
                int c = v % 10;
                if(c > 0){
                    int temp = x - pow10;
                    if(!prime[temp] && disX + temp < dis[temp]){
                        dis[temp] = disX + temp;
                        queue.add(new int[]{temp, disX + temp});
                    }
                }
                v /= 10;
                pow10 *= 10;
            }
        }
        return -1;
    }
}
